【基础算法】刷题记录 2018-03-23

发表于
字数统计: 803 字 | 阅读时长 ≈ 4 分钟
  • 最长回文子字符串
  • 回文数字
  • 最大多位数串
  • 逆序整数

最长回文子字符串

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路

显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢？答案是肯定的。我们知道整个字符串中的所有字符，以及字符间的空隙，都可能是某个回文子串的对称轴位置。可以遍历这些位置，在每个位置上同时向左和向右扩展，直到左右两边的字符不同，或者达到边界。对于一个长度为n的字符串，这样的位置一共有n+n-1=2n-1个，在每个位置上平均大约要进行n/4次字符比较，于是此算法的时间复杂度是O(n^2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String longestPalindrome(String s) {
        int max_len = 1;
        int start=0;
        for(int i=0; i<s.length(); i++){
            int len=0;
            if(i+1<s.length() && (s.charAt(i+1)==s.charAt(i))){
                len =2;
                if(len>max_len){
                    max_len = len;
                    start = i;
                }
                while((i+len)<s.length() && i-len+1>=0 && (s.charAt(i-len+1) == s.charAt(i+len))){
                    len++;
                    if(len*2-2 > max_len){
                        max_len = len*2-2;
                        start = i-len+2;
                    }
                }
            }
            if(i+1<s.length()){
                len =1;
                while(i+len<s.length() && i-len>=0 && s.charAt(i-len)==s.charAt(i+len)){
                    len++;
                    if((len*2-1)>max_len){
                        max_len = len*2 -1;
                        start = i-len+1;
                    }
                }
            } 
        }
        return s.substring(start, start+max_len);
    }
}

回文数字

问题

Determine whether an integer is a palindrome. Do this without extra space.

技巧点

将原数字倒转一半，判断前一半数字是否相同

易错点

10及其倍数的处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPalindrome(int x) {
    if(x<0 ||(x%10==0&&x!=0)){
        return false;
    }else{
        int rx=0;
        while(x>rx){
            int digit = x%10;
            x = x/10;
            rx = rx*10+digit;
        }
        if(x==rx || x==rx/10){
            return true;
        }else{
            return false;
        }
    }
}

最大多位数串

问题

设有n个正整数，将他们连接成一排，组成一个最大的多位整数。

如:n=3时，3个整数13,312,343,连成的最大整数为34331213。

如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。

思路

本题可以理解为对N个数进行排序，只不过排序的标准不是数值的大小，而是两个字符串组合到一起转化成整形后的数值大小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(string i, string j){
    return (i+j)>(j+i);
}
int main(){
    int n;
    while(cin>>n){
        vector<string>arr(n,"");
            for(int i =0; i< n; i++){
            cin>>arr[i];
        }
        sort(arr.begin(),arr.end(),compare);
        for(int i=0; i<n; i++){
            cout<<arr[i];
        }
    }
    return 0;
}

注意点

  1. vector容器（构造函数参数，常用函数）
  2. sort函数（algorithm头文件）

逆序整数

题目

Given a 32-bit signed integer, reverse digits of an integer.

易错点

  1. 负数的逆序
  2. 逆序后发生溢出

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        int reverse(int x) {
            int rx=0;
            int sign=0;
            if(x>=0){
                sign = 1;
            }else{
                sign = -1;
                x =-x;
            }
            while(x!=0){
                int digit = x%10;
                int old_rx = rx;
                rx = rx*10+digit;
                if(rx/10 != old_rx){
                    return 0;
                }else{
                    x = x/10;
                } 
            }
            return rx*sign;
        }
    };